1. Field of Invention
The present invention relates generally to the field of automated design techniques, and more particularly to methods and systems for routing and matching signal nets in integrated circuits.
2. Background of the Invention
As VLSI fabrication technology reaches submicron device dimensions and circuit speeds falls below sub-nanosecond, interconnect delays become the dominant factor in determining circuit performance. Further, as integrated circuit designs increase in size, interconnect delays between circuit cells become larger and account for an increasing percentage of total circuit delay. To ensure circuit performance under these critical conditions, signal nets connecting circuit cells typically have time delay constraints. During circuit design, the delay constraints are usually translated into minimum and maximal wire length constraints in a layout system. The problem of routing the signal nets to satisfy the delay constraints can then be stated as follows: given a placement of various cells, how to route a given set of signal nets to a wire length between the maximal and minimal wire length constraints.
During delay routing, some signal nets must be matched. Signal net matching is the process of ensuring that the nets in given matching set of signal nets are connected by specified length wires, within a given tolerance. Signal net matching is used to eliminate clock skew and racing, to match the paths of circuit cells having differential drivers, and to ensure simultaneous output switching of cells, e.g. for outputs arriving simultaneously at a data bus or other circuit element.
Current delay routers suffer methodological limitations that in turn result in implementation deficiencies. First, existing routers solve the routing problem using only the delay constraints, independent of other layout considerations. When such routers are integrated into a layout system, they are invoked either in a pre-routing stage or in an after-routing (post-process) stage. Thus, the overall layout system performance is severely degraded, for example, by a decrease in the interconnect completion rate or an increase in the CPU time required for routing.
Another methodological problem with existing delay routers is their inability to produce arrangements that completely satisfy all delay constraints. A typical delay routing approach having this problem is to weigh the signal nets, i.e. net priorities are assigned based on a static timing analysis. Signal nets with larger weights are processed earlier and the wire lengths are controlled by a routing cost function. Generally, several routing iterations are needed to achieve a reasonably good result by adjusting signal net weights such that most of the signal nets will meet the delay requirements. However, an optimal solution generally cannot be determined because of the extensive CPU time needed for computation, and the convergence problem. Accordingly, most of the practical layout systems use a special delay router, which generally have the following limitations.
There are basically two methods for connecting two points with a specified length of wire: 1) Find a path from the start point to the end point, then adjust the wire length; 2) Find a path from the start point to the end point, controlling the wire length at the same time. In method 1, if the delay net (the added path that satisfies the delay constraints) is routed first, the length adjustment will almost guarantee that the delay contraints are satisfied in a typical design. However, the added wire length for the delay net will occupy a large amount of routing space, thereby significantly increasing the probability that the whole design cannot be fully routed. This is an unacceptable practice because the main objective of layout routing is to complete all connections. 0n the other hand, if the wire length of the delay net is adjusted using free space after all signal nets have been routed, the routability will not be affected. However, after routing, there is not much free space available for changing the wire length to satisfy the delay constraints. Thus, a large number of delay nets fail to reach their specified length in a typical design because of existing wires, although a feasible solution exists.
Method 2 is more appealing methodologically than method 1, but it is a well-known fact that tracking wire length during maze or geometry-based routing is very expensive in CPU time, especially in non-uniform grid or gridless environments. Various approaches have been adopted to surmount this difficulty, without sufficient success. For example, diamond routing iteratively selects a random detour point on a truncated diamond and attempts to route from the start point to the end point through the detour point. This approach is of limited practical application because of the impossibility of selecting and searching through all detour points. Also, only two pin nets can be handled by typical diamond routers.
It is desirable therefore to provide a delay router that overcomes the limitations of existing routers. Specifically, it is desirable to provide a delay router that provides complete routing solutions without extensive CPU time, and without limiting the interconnect completion rate. Further, it is desirable to provide a delay router that can match signal nets during the delay routing process. Finally, it is desirable to provide a delay router that is adaptable to a variety of existing design environments.